/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package practice.v2;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:QuickSort.java v1.0 2018/8/15 上午11:25 LvJing Exp $
 */
public class QuickSort {

    /**
     * 快速排序：属于交换排序类型，第一趟确定第一个数最终的位置并完成交换，保证该数前面全是小于它的，后面全是大于它的，
     * 后面拆分成确定该数前半段和后半段的第一个数的位置。。。以此递归
     */
    public void quickSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1)
            return;

        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int middle = getMiddle(arr, start, end);
            quickSort(arr, start, middle - 1);
            quickSort(arr, middle + 1, end);
        }
    }

    private int getMiddle(int[] arr, int start, int end) {
        int middleValue = arr[start];
        while (start < end) {
            // 先从右往左判断，发现有比temp小的，交换到start位置
            while (start < end && arr[end] >= middleValue)
                end--;
            if (start < end)
                swap(arr, start, end);
            else break;

            // 再从左往右判断，发现有比temp大的，交换到end位置
            while (start < end && arr[start] <= middleValue)
                start++;
            if (start < end)
                swap(arr, start, end);
            else break;
        }
        return start;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test01() {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++)
            arr[i] = random.nextInt(100);
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
